Міністерство освіти і науки, молоді та спорту України
Національний Університет «Львівська Політехніка»
Кафедра ЕОМ
Звіт
до лабораторна робота № 4
з дисципліни : «Паралельні та розподілені обчислення»
на тему: «Можливості використання паралельних алгоритмів»
Варіант 20
Львів - 2011
Мета: Дослідити можливості розв’язання різноманітних задач за допомогою паралельних алгоритмів. Навчитися виділяти незалежні гілки обчислень та виконувати їх паралельно.
Завдання.
8,
22
В полі 8*8 кліток зображено кілька прямокутників, кожен з яких складається з кліток, різні прямокутники не перетинаються і не доторкаються один до одного. Задана квадратна матриця порядку 8, в якій елемент рівний нулю, якщо відповідна клітина належить прямокутнику і відмінний від нуля, в іншому випадку. Визначити кількість прямокутників. Початковими даними вважати матрицю елементів, яка повинна вводитися під час виконання програми. Графічно відобразити вхідні дані.
Аналіз задачі та опис незалежних подій.
В даній задачі можна виділити n незалежних гілок, які можна виконувати паралельно з основною програмою – це вибір квадрату та перевірка чи в ньому різні числа. Для цього на вхід функції, що визначає квадрат, йде структура даних, яка описує матрицю. Пошук прямокутників з різними числами йде послідовно.
Текст програми.
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.IO;
using System.Windows.Forms;
using System.Threading;
namespace lab4
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
private void randMATRIX(DataGridView d)
{
string[] mass = File.ReadAllLines("matrix.txt");
for (int p = 0; p < mass.Length; p++)
{
int[] m = mass[p].Split(new char[] { ' ' },
StringSplitOptions.RemoveEmptyEntries).Select(s => int.Parse(s)).ToArray();
for (int i = 0; i < m.Length; i++)
{
d[i, p].Value = m[i];
}
}
}
private void dataGridView1_CellContentClick(object sender, DataGridViewCellEventArgs e)
{
dataGridView1.Enabled = true;
}
private void rect_bounds(DataGridView d, int a, int b, ref int[] A)
{
int i, j;
i = a;
j = b;
int size = 8;
while (j >= 0 && Convert.ToInt32(d[j, i].Value) == 0)
j -= 1;
j += 1;
while (i >= 0 && Convert.ToInt32(d[j, i].Value) == 0)
i -= 1;
A[0] = i + 1;
A[1] = j;
i = a; j = b;
while (j < size && Convert.ToInt32(d[j, i].Value) == 0)
j += 1;
j -= 1;
while (i < size && Convert.ToInt32(d[j, i].Value) == 0)
i += 1;
A[2] = i - 1;
A[3] = j;
}
private void erase_rect(DataGridView d, ref int[] A, ref int count, Color col)
{
for (int i = A[0]; i <= A[2]; i++)
for (int j = A[1]; j <= A[3]; j++)
d[j, i].Style.BackColor = col;
count++;
}
private int calculate_rects(DataGridView d)
{
int[] A = new int[4];
Color[] col = new Color[]{Color.Lime,Color.Red,Color.Orange,Color.LightGreen,Color.Blue,
Color.Brown,Color.Gray,Color.Green,Color.LightBlue,Color.Silver,Color.Yellow,
Color.DarkRed,Color.Gold,Color.GreenYellow,Color.LightCyan};
int[] dopMas = new int[col.Length];
int size = 8;
int count = 0;
int j, node, l = 0;
for (int i = 0; i < size; i++)
{
j = 0;
while (j < size)
{
node = Conver...